public class MySingleList {
    /**
     * 这是一个链表
     */
        static class Node{  // 是不是静态内部类就看自己需求了
            // 以为节点是链表组成的一部分，节点也是一个类
            // 需要把节点定义成一个内部类
            public int val; // 存储数据
            public Node next; // 存储下一个节点的地址

            // 设置成静态类的好处就是，如果在类外还需要使用这个类的话。呢就不需要对象了 ， 生成Node对象的时候不依赖外部对象
            public Node(int val){
                this.val = val;  // 数据可以先构造
                // 不给next
                // 因为一开始根本就不知到next是谁
                // 需要用逻辑实现

            }
        }
        // 接下来创建head对象
        public Node head; // 代表当前链表的头节点
        // 看head引用谁了


        //创建一个链表,假设有四个节点
        public void createLink(){
            // 四个节点 ，
            Node node1 = new Node(12);
            Node node2 = new Node(45);
            Node node3 = new Node(23);
            Node node4 = new Node(90);

            //给next赋值
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            head = node1;
        }

        // 首先遍历链表
        public void display(){
            // 从head开始往后遍历
            Node cur = head;
            // 问题是head怎么往后走
            while( /*head != null*/  cur !=  null ){  // 条件是head！=null ， 如果是head.next ！= null 会少打印一个
                // 但是如果说是 head != null 那么最后你会发现 头节点找不到了，头节点为null了现在 ， 打印两次只有一次的结果
                // 所以要在定义一个变量 cur ， 让cur来动
                // System.out.print(head.val+" ");
                System.out.print(cur.val+" ");
                //head = head.next; // head往后走
                cur = cur.next;
            }
            // 结论： 如果说 把整个链表遍历完成 则是 head == null
            //       如果说 只遍历到链表的尾巴 则是 head.next == null
            System.out.println();
        }

        // 从指定位置打印链表
        public void display(Node newHead){
            Node cur = newHead;
            while( /*head != null*/  cur !=  null ){
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }

        //查找是否包含关键字key是否在链表当中
        public boolean contains(int key){
            // 需要从头去遍历这个链表
            Node cur = head;
            while(cur!=null){
                if(cur.val == key){  // 这个因为val是int类型的所以用 ==
                    // 如果是引用类型的话不能用等号了，要用 .equals()
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

        // 得到链表的长度  //时间复杂度是O(N)
        public int size(){
            int count = 0;
            Node cur = head;
            while(cur!=null){
                count++;
                cur = cur.next;
            }
            return count;
        }

        //头插法
        // 意思就是把一个新节点插入到当前列表的头部

        // 插入数据
        // 1.得有节点
        // 2.要修改两个地方 ， 新节点的next的值要改， 之前的head的值要改
        public void addFirst(int data){
            Node node = new Node(data); // 建立新节点
        /*
        head = node;
        node.next = head ;
        * */  // 这样写是错误的，写反了，这个是自己指向自己
            // 应该这样写
            node.next = head;
            head = node;
            // 应该先绑后面然后再管其他的
        }

        //尾插法
        // 把节点插入到该链表的尾部
        // 需要修改 最后一个节点的next的值，再改新节点的next的值
        public void addLast(int data){
            Node node = new Node(data);
            // 如何找到最后一个节点的值
            // 需要定义一个cur
            // 先判断head是否为null
            if(head == null){
                head = node;
                return;
            }
            Node cur = head;
            while(cur.next!=null){  //找到最后一个节点的位置
                cur = cur.next;
            }
            cur.next = node;
            //但是head如果是null的话
            // 拿这个代码插入是错误的
            // 应该再这样写先判断head是否为空
        }
        // 总结：链表 的插入只是修改指向


        //任意位置插入，第一个数据节点为0号的下标
        //则是将前一个节点的next值改成这个新节点的值
        // 再将这个新节点的next值改成后一个节点的值
        // 那么如何找到要插入的该位置呢
        // 就是要往哪一个位置插就让cur走到呢个位置的前一个节点 index-1
        // node.next = cur.next;
        // cur.next = node;
        // 关键就是要找到cur
        public  void addIndex(int index,int data){
            Node node = new Node(data);
            //先检查index
            checkIndex(index);
            //再判断index的值
            if (index == 0){
                addFirst(data);
                return;
            }
            if(index == size()){
                addLast(data);
                return;
            }
            //考虑中间值
        /*Node cur = head;
        int count = 0;
        while(count!=index-1) {
            cur = cur.next;
            count++;
        }*/
            //将这一段用一个方法来表示
            Node cur = findIndexSubOne(index);
            node.next = cur.next;  // 一定要先绑后面的
            cur.next = node;
        }
        // 然后判断index是否合法
        private  void checkIndex(int index) throws IndexOutOfException{
            if(index<0||index>size()){
                throw new IndexOutOfException("index位置不合法");
            }
        }
        //考虑中间值

        /**
         * 找到index-1位置节点的地址
         * @param index
         * @return
         */
        public Node findIndexSubOne(int index){
            Node cur = head;
            int count = 0;
            while(count!=index-1){
                cur = cur.next;
                count++;
            }
            return cur;
        }


        //删除第一次出现关键字为key的节点
        // 删除该节点就是跳过该节点
        //将该节点前一个节点的地址直接换成指向后面节点的地址
        // 所以cur要走到删除节点的前一个地方
        // cur.next = del.next;  或者 cur.next = cur.next.next;  // 这个代码不影响最后一个节点
        // 但是删除第一个元素也是一个问题，第一个元素没有前驱
        // 所以先判断head需不需要删除
        //

        public void remove(int key){

            //先判断头节点是否要删除
            if(head.val == key){
                head = head.next;
                return;
            }
            //接下来找到要删除节点的前一个节点
            Node cur = searchPrey(key); // 代表当前的节点
            if (cur == null){
                return;
            }
            Node del = cur.next;// 代表要删除的节点
            cur.next = del.next;
        }
        //接下来找到要删除节点的前一个节点

        /**
         * 找到关键字key的前一个节点
         * @param key
         * @return
         */
        private  Node searchPrey(int key){
            //要判断head 是否为null
            if (head == null){
                return null; // 一个节点都没有
            }
            Node cur = head;
            while(cur.next != null){ //cur.next.val 代表要删除节点位置的数据，而此时的cur还是指向前一个节点的位置
                // 要考虑key是否在链表种能够找到
                //**** 当cur.next == null 时说明没有找到 ****
                if (cur.next.val == key){
                    return cur;
                }
                cur = cur.next;

            }
            return null; //代表没有你要删除的节点
        }


        //删除所有key的节点
        // 定义一个cur ，定义一个prev
        // cur代表当前节点是否要被删除
        // prev记录cur的位置
        public void removeAllKey(int key){
            if (head == null){
                return;
            }
            Node prev = head;
            Node cur = head.next;
            while(cur != null){
                if(cur.val == key){
                    prev.next = cur.next;
                    cur = cur.next; // 让cur往后走，prev不动
                }else{
                    prev = cur;//不等于的话，让prev走到cur的位置
                    cur=cur.next;//之后cur 继续往后走，直到cur == null
                }
            }
            //但是如果prev的位置上也是要删除的目标值的话、
            //值依靠这个 呢就不会被删除
            //所以要进行判断 ， 这个判断如果写在前面几行的话要用while来进行判断
            // 如果时经过删除后，再放后面进行判断的话用if就可以
            if(head.val == key){
                head = head.next;
            }
        }

        //清空链表

        /**
         * 表示链表的每个节点都要被回收
         */
        //只要第一个节点没有被指向的话。剩余的节点都将会被回收
        public void clear(){
            head = null;
        }

        //链表的反转
        public Node reverseList() {
            if(head == null){
                return null;
            }
            /*if(head.next = null){
                return = head;
            }*/
            Node cur = head.next;
            head.next = null;
            while(cur!=null){
                Node next = cur.next;
                cur.next = head;
                head = cur;
                cur = next;
            }
            return head;
        }
        //找链表的中间值
        public  Node middleNode(){
            // 定义两个节点。让第一个节点的移动速度是第二个节点移动速度的二倍
            // 但必须是走两步走一步，不能是走四步走两步等后面的
            Node fast  = head;
            Node slow = head;
            while(fast!=null&&fast.next!=null){  //这两个条件还不能互换 , 因为 必须先判断fast是否为null才能知道fast.null;
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;

        }

    //找到倒数第K个节点
    // 要求只遍历一遍列表
    // 也是用快慢来求 fast slow
    // 倒数第K个节点 fast 和 slow 之前差k-1步
    // 所以让fast先走k-1步之后   再 fast和slow开始一步一步走
    // 当fast所指的next为空的时候 slow指的位置就是倒数第k个位置
    public Node FindKthToTail(int k){
            //要先判断k的合法性
        /*if(k<=0||k>size()||head == null){
            return null;
        }*/

        // 也可以不用size()方法来判断k
        if (k<=0|| head == null){
            return null;
        }

        Node fast = head;
        Node slow = head;

        //先让fast走k-1步
        while(k-1!=0){
            fast = fast.next;

            //用k不加size()方法来判定k的合法性
            if(fast == null){
                return null;
            }

            k--;
        }

        //第二步和第三步，让fast和slow一起一步一步走
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    //合并两个有序的链表
     // 先申请一个虚拟节点,这个节点不具备参考性
    // newHead 是合并好之后的头节点,叫做tmp
    // tmp的位置是记录当前链接的位置
    // if(head1.val<head2.val){}else{}
    // 前提是两个链表都有节点
    // 只要有一个为空表示至少有一个链表已经安排完了
    // 此时还会剩余一个链表的后半部分


    //回文链表
    // 奇数链表
    // 先找到链表的中间节点
    // 再将从中间位置开始以后的节点反转
    public boolean chkPalindrome(){
            if(head==null){
                return false;
            }
            if(head.next==null){
                return true;
            }
         //1.先找中间的节点 . 前面有
        Node fast = head;
        Node slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 2.翻转
        Node cur = slow.next; // 代表当前要反转的节点
        while(cur!=null){
            Node curNext = cur.next; // 先记录cur.next
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // 3 .一个头往后，一个从后往前
        while(slow!=head){
            if(slow.val!=head.val){
                return false;
            }
            if(head.next == slow){
                return true;  //判断偶数节点情况
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
        // 但是偶数节点在这个地方有问题 第三步slow和head会错过去
        // 所以要先判断一下
    }

}

